﻿namespace BinarySearch;

public class LC0035 {
    public int SearchInsert(int[] nums, int target) {
        int N = nums.Length;
        int left = 0, right = N, mid = (left + right) / 2;
        while (left < right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return left; // 一定有left==right，且恰好为插入位置
    }

    /// <summary>
    /// 相比上一种实现，这种实现的主要区别在于，right指针恰好指向区间的右边界
    /// </summary>
    public int SearchInsert2(int[] nums, int target) {
        int N = nums.Length;
        int left = 0, right = N - 1, mid = (left + right) / 2;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        } // 此时应有right==left-1

        return left; // 如果无法找到，那么left指向应该插入的位置
    }
}